#! /usr/bin/python


class heap(object):

    def __init__(self, priority):
        self._priofunc, self._data = priority, []

    def push(self, value):
        self._data.append(value)

        index, prio = len(self._data) - 1, self._priofunc(value)

        while index > 0:
            parent_index = self.__parent(index)
            if self.__priority(parent_index) > prio:
                self.__swap(index, parent_index)
                index = parent_index
            else:
                break

    def pop(self):
        if not self._data:
            return
        elif len(self._data) == 1:
            self._data = []
        else:
            self._data[0] = self._data[-1]
            self._data = self._data[:-1]

            index, prio = 0, self.__priority(0)
            while index <= (len(self._data) - 1) / 2:
                li, ri = self.__left(index), self.__right(index)

                if li >= len(self._data):
                    break

                if ri >= len(self._data):
                    if self.__priority(li) < prio:
                        self.__swap(li, index)
                    break

                lp, rp = self.__priority(li), self.__priority(ri)

                if lp < rp:
                    mni, mxi = li, ri
                    mnp, mxp = lp, rp
                else:
                    mni, mxi = ri, li
                    mnp, mxp = rp, lp

                if prio < mnp:
                    break
                else:
                    self.__swap(mni, index)
                    index = mni

    def top(self):
        return self._data[0] if self._data else None

    def __priority(self, index):
        return self._priofunc(self._data[index])

    def __swap(self, i0, i1):
        self._data[i0], self._data[i1] = self._data[i1], self._data[i0]

    def __len__(self):
        return len(self._data)

    @staticmethod
    def __left(index):
        return 2 * index + 1

    @staticmethod
    def __right(index):
        return 2 * index + 2

    @staticmethod
    def __parent(index):
        return (index - 1) / 2


if __name__ == '__main__':

    def prio(x):
        return x[0]

    def test_heap():
        h = heap(prio)
        h.push((5, 5))
        h.push((20, 2))
        h.push((3, 3))
        h.push((30, 3))
        h.push((10, 1))
        h.push((4, 4))
        print h._data

        while True:
            top = h.top()
            if top is None:
                break
            print top
            h.pop()

    test_heap()
